// 08-图9 关键活动
#include "../base/MGraph-ToSort.c"
#include "../base/MGraph-input.c"

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 建立初始为最大权重的有向图
    MGraph* g = createGraph(DirectedGraph, MaxWeight, n);
    // 读取 m 条边
    readEdgeV1WithWeight(g, m);
    printGraph(g);

    int* topOrder = (int*)calloc(n, sizeof(int));
    int* earliest = (int*)calloc(n, sizeof(int));
    int* latest = (int*)calloc(n, sizeof(int));
    Edge* path = (Edge*)calloc(m, sizeof(Edge));
    if (topSort(g, topOrder, earliest)) {
        int maxTime = findMax(earliest, n);
        printf("%d\n", maxTime);
        calLatest(g, latest, maxTime);
        print1D("earliest", earliest, g->vertexNum);
        print1D("latest", latest, g->vertexNum);
        int pathNum = calImportantPath(g, earliest, latest, path);
        for (int i=0; i<pathNum; i++) {
            printf("%d->%d\n", path[i].v+1, path[i].w+1);
        }
    } else {
        printf("0\n");
    }

    free(topOrder);
    free(earliest);
    free(path);
    freeGraph(g);
    return 0;
}
